package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/odd-even-linked-list/description/
 * <p>
 * <p>
 * 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别分组，保持它们原有的相对顺序，然后把偶数索引节点分组连接到奇数索引节点分组之后，返回重新排序的链表。
 * <p>
 * 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
 * <p>
 * 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
 * <p>
 * 你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
 */
public class L_328_奇偶链表 {

    public static void main(String[] args) {
        ListNode  head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);
        head.next.next.next.next.next.next = new ListNode(7);
        ListNode head1 = oddEvenList(head);
        ListNode.print(head1);
    }

    /**
     * 思路：
     * 从题意可知，需要将偶数链表放在奇数尾部
     * <p>
     * 涉及以下操作：
     * 1. 将链表分为两个链表，一个奇数，一个偶数
     * 2. 每次遍历原链表后，将偶数节点摘出来，形成新的链表
     * 3. 将偶数链表连接后原链表后面
     *
     * @param head
     * @return
     */
    public static ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        int count = 0;
        ListNode oddHead = null;
        ListNode oddCurr = null;

        ListNode prev = null;
        ListNode curr = head;
        ListNode tail = null;
        while (curr != null) {
            ListNode next = curr.next;
            count++;
            if (count % 2 == 0) {
                if (next == null) {
                    tail = prev;
                }

                if (oddHead == null) {
                    oddHead = curr;
                    oddCurr = oddHead;
                } else {
                    oddCurr.next = curr;
                    oddCurr = oddCurr.next;
                }

                // 从原链表删除
                prev.next = curr.next;
                curr.next = null;
            } else {
                if (next == null) {
                    tail = curr;
                }
            }

            prev = curr;
            curr = next;
        }

        tail.next = oddHead;
        return head;
    }
}
